package List;
import java.util.*;

public class Test {
    public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if(headA == null) return headB;
        if(headB == null) return headA;
        if(headA == null && headB == null) return null;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }
        if(headA == null) {
            tmp.next = headB;
        }
        if(headB == null) {
            tmp.next = headA;
        }
        return newHead.next;
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null) {
            return null;
        }
        if(headB == null) {
            return null;
        }
        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;
        ListNode ps = headB;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA-lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB-lenA;
        }
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null && ps == null) {
            return null;
        }
        return pl;
    }
    public static void createCute(ListNode headA, ListNode headB) {
        headB.next.next = headA.next.next;
    }
    public static void main(String[] args) {
        MyRealinkedList myRealLinkedList = new MyRealinkedList();
        myRealLinkedList.addLast(1);
        myRealLinkedList.addLast(1);
        myRealLinkedList.addLast(1);
        myRealLinkedList.addLast(1);
        myRealLinkedList.display();
        myRealLinkedList.clear();
        System.out.println("==================");
    }
    public static void main3(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.addLast(11);
        myLinkedList.show();
        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(8);
        myLinkedList2.show();
        createCute(myLinkedList.head,myLinkedList2.head);
        ListNode ret = getIntersectionNode(myLinkedList.head,myLinkedList2.head);
        System.out.println(ret.val);
    }
    public static void main2(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.show();
        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(8);
        myLinkedList2.show();
        ListNode ret =  mergeTwoLists(myLinkedList.head,myLinkedList2.head);
        myLinkedList.show2(ret);
    }
    public static void main1(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(11);
        myLinkedList.addLast(21);
        myLinkedList.addLast(8);
        myLinkedList.addLast(4);
        myLinkedList.show();
        myLinkedList.createCycle();
        System.out.println(myLinkedList.hasCycle());
        ListNode ret2 = myLinkedList.detectCycle();
        System.out.println(ret2.val);
    }
}